|
In the mathematical theory of matroids, a minor of a matroid ''M'' is another matroid ''N'' that is obtained from ''M'' by a sequence of restriction and contraction operations. Matroid minors are closely related to graph minors, and the restriction and contraction operations by which they are formed correspond to edge deletion and edge contraction operations in graphs. The theory of matroid minors leads to structural decompositions of matroids, and characterizations of matroid families by forbidden minors, analogous to the corresponding theory in graphs. ==Definitions== If ''S'' is a subset of ''E'', the restriction of ''M'' to ''S'', written ''M'' |''S'', is the matroid on the set ''S'' whose independent sets are the independent sets of ''M'' that are contained in ''S''. Its circuits are the circuits of ''M'' that are contained in ''S'' and its rank function is that of ''M'' restricted to subsets of ''S''. If ''T'' is an independent subset of ''E'', the contraction of ''M'' by ''T'', written ''M''/''T'', is the matroid on the underlying set ''E − T'' whose independent sets are the sets whose union with ''T'' is independent in ''M''. This definition may be extended to arbitrary ''T'' by choosing a basis for ''T'' and defining a set to be independent in the contraction if its union with this basis remains independent in ''M''. The rank function of the contraction is A matroid ''N'' is a minor of a matroid ''M'' if it can be constructed from ''M'' by restriction and contraction operations. In terms of the geometric lattice formed by the flats of a matroid, taking a minor of a matroid corresponds to taking an interval of the lattice, the part of the lattice lying between a given lower bound and upper bound element. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「matroid minor」の詳細全文を読む スポンサード リンク
|